public class test3 {
    class Solution {
        boolean[][] used;
        public boolean exist(char[][] board, String word) {
            boolean res = false;
            used = new boolean[board.length][board[0].length];
            for(int i = 0;i<board.length;i++){
                for(int j = 0;j<board[0].length;j++){
                    if(word.charAt(0)==board[i][j]){
                        //找到一个开头
                        res =  res || backTracking(board,word,i,j,0);
                    }
                }
            }
            return res;
        }
        private boolean backTracking(char[][] board, String word,int row,int col,int start){
            //找到一种完整吻合的方案
            if(start==word.length()){
                return true;
            }
            //越界或者用了已经用过的字符，无效
            if(row<0 || row>=board.length || col<0 || col>=board[0].length || used[row][col]){
                return false;
            }

            if(word.charAt(start)!=board[row][col]){
                return false;
            }
            used[row][col] = true;
            boolean res = backTracking(board,word,row+1,col,start+1) ||
                    backTracking(board,word,row-1,col,start+1) ||
                    backTracking(board,word,row,col+1,start+1) ||
                    backTracking(board,word,row,col-1,start+1) ;
            used[row][col] = false;

            return res;
        }
    }
}
